package dp;

import java.util.Arrays;

/**
 * @author ZJX
 * @version 1.0
 * @descption
 * @since 2025/9/27 11:49
 */
public class T {
    public boolean wiggleMaxLength(int[] nums) {
        if (nums.length < 2) {
            return true;  // 长度小于2，直接认为可以形成摆动序列
        }

        // 两个状态：up 表示上升，down 表示下降
        boolean up = false, down = false;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                // 如果当前元素大于前一个元素，说明是上升
                if (!up) {
                    up = true;
                    down = false; // 重置下降状态
                }
            } else if (nums[i] < nums[i - 1]) {
                // 如果当前元素小于前一个元素，说明是下降
                if (!down) {
                    down = true;
                    up = false;  // 重置上升状态
                }
            }
        }

        // 如果存在交替变化，返回 true，否则返回 false
        return up || down;
    }

    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }

        int n = ratings.length;
        int[] candies = new int[n];

        // 每个学生至少一个糖果
        Arrays.fill(candies, 1);

        // 从左到右遍历
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 从右到左遍历
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        // 计算总糖果数
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }

    public String reorganizeString(String s) {
        int n = s.length();
        int[] count = new int[26]; // 统计每个字母出现的次数（a-z）

        // 1. 统计频率
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }

        // 2. 找出出现次数最多的字符
        int maxCount = 0, letter = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > maxCount) {
                maxCount = count[i];
                letter = i; // 记录下标（字母）
            }
        }

        // 3. 如果某个字符出现次数 > (n+1)/2，就无法排开 → 返回空
        // 例如：s = "aaaab"，a 出现 4 次，长度=5，(5+1)/2=3 → 4 > 3 → 不可能
        if (maxCount > (n + 1) / 2)
            return "";

        char[] res = new char[n]; // 存结果
        int idx = 0; // 用来填字符的位置

        // 4. 先放置出现次数最多的那个字符，放在偶数下标(0,2,4,...)上
        //    这样能最大限度拉开它们之间的间隔
        while (count[letter] > 0) {
            res[idx] = (char) (letter + 'a'); // 把字母放入结果
            idx += 2; // 每次往后跳2个位置
            count[letter]--; // 用掉一个
        }

        // 5. 再放剩余的字符
        for (int i = 0; i < 26; i++) {
            while (count[i] > 0) {
                // 如果偶数位置填满了，就换到奇数位置(1,3,5,...)
                if (idx >= n)
                    idx = 1;
                res[idx] = (char) (i + 'a');
                idx += 2;
                count[i]--;
            }
        }

        // 6. 返回结果
        return new String(res);
    }

    /**
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其有最大和的数组
     * 力扣 53 变种题
     *
     * @param nums 输入的数组
     * @return 返回最大和的数组
     */
    public int[] maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int maxSum = dp[0];
        int start = 0, end = 0, tempStart = 0;
        for (int i = 1; i < n; i++) {
            if (dp[i - 1] + nums[i] > nums[i]) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
                tempStart = i;
            }
            if (dp[i] > maxSum) {
                maxSum = dp[i];
                start = tempStart;
                end = i;
            }
        }
        return Arrays.copyOfRange(nums, start, end + 1);
    }

    public int maxProduct(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        int max = nums[0];
        int min = nums[0];
        int ret = nums[0];
        for (int i = 1; i < n; i++) {
            int preMax = max;
            int preMin = min;
            max = Math.max(nums[i], Math.max(preMax * nums[i], preMin * nums[i]));
            min = Math.min(nums[i], Math.min(preMax * nums[i], preMin * nums[i]));
            ret = Math.max(ret, max);
        }
        return ret;
    }

    /**
     * 解密
     *
     * @param s 字符串
     * @return 方法次数
     */
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= n; i++) {
            char c1 = s.charAt(i - 1);
            char c2 = s.charAt(i - 2);
            if (c1 != '0') {
                dp[i] += dp[i - 1];
            }
            if (c2 == '1' || (c2 == '2' && c1 <= '6')) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }

    /**
     * 力扣 按摩师
     *
     * @param nums
     * @return
     */
    public int massage(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[n];
    }

    /**
     * 力扣 740
     *
     * @param nums
     * @return
     */
    public int deleteAndEarn(int[] nums) {
        int max = 0;
        for (int n : nums) {
            max = Math.max(n, max);
        }
        int[] point = new int[max + 1];
        for (int num : nums) {
            point[num] += num;
        }
        int[] dp = new int[max + 1];
        dp[0] = 0;
        dp[1] = point[1];
        for (int i = 2; i <= max; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + point[i]);
        }
        return dp[max];
    }

    /**
     * 01 背包
     *
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 == 1) return false;
        int target = total / 2;

        // 检查是否有元素大于目标值
        for (int num : nums) {
            if (num > target) {
                return false;
            }
        }
        boolean[] dp = new boolean[target + 1]; // dp表示 能否组成和为j的数组
        dp[0] = true;
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }


    public static void main(String[] args) {
        T t = new T();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(Arrays.toString(t.maxSubArray(nums)));
    }
}

